The Zebra Puzzle

by

Jaime Rangel-Mondragón
 Arturo González-Gutiérrez

aglez@uaq.mx

Introduction

Consider the following logic puzzle that has achieved celebrity for its difficulty (and also because it was attributed to Albert Einstein [1], who also supposedly said only 2% of humans could solve it). and used in textbooks on discrete maths to show the workings of applying premises to arrive at conclusions in a logical way. The authors think it is a fun way to learn commands that manipulate patterns, mainly DeleteCases and Cases. The zebra problem [2] is as follows.

There are five men, all with different nationalities, jobs, pets and favorite drinks, living in houses of different colors and numbers. The following facts are known:

The Englishman lives in the red house.

The Spaniard owns the dog.

The Japanese is a painter.

The Italian drinks tea.

The Norwegian lives in the first house on the left.

The photographer breeds snails.

The diplomat lives in the yellow house.

Milk is drunk in the middle house.

The owner of the green house drinks coffee.

The violinist drinks orange juice.

The Norwegian´s house is next to the blue one.

The fox is in a house next to that of the physician.

The horse is in a house next to that of the diplomat.

The green house is to the right of the white house.

The problem is to find out who owns the zebra (hence the name of the puzzle) from those clues.

Solving the problem

Let us start by defining variables (note that the zebra was not mentioned in the clues so its presence has to be infered)

nationalities = {English, Spaniard, Japanese, Italian, Norwegian};
jobs = {painter, photographer, diplomat, violinist, physician};
pets = {zebra, dog, snails, fox, horse};
drinks = {mineralWater, tea, milk, coffee, orangeJuice};
colors = {red, yellow, green, blue, white};
houses = {1, 2, 3, 4, 5};

We might consider all (5^6)=15625 sets of possibilities for each people included encapsulated in variable u:

u=Flatten[Outer[List,nationalities,jobs,pets,drinks,colors,houses],5];
Length[u]
Short[u,4]

But to select five elements from this list we confront too many choices:

Binomial[15625,5]

So, we are forced to adopt an alternative strategy. Let us see how each of the clues allow us to succesively trim variable u.

The Englishman lives in the red house.

u1=DeleteCases[u,{English,__,Except[red],_}|{Except[English],__,red,_}];
Length[u1]

Note that if we use the following code we will overtrim u.

Cases[u,{English,__,red,_}];
Length[%]

The Spaniard owns the dog.

u2=DeleteCases[u1,{Spaniard,_,Except[dog],__}|{Except[Spaniard],_,dog,__}];
Length[u2]

The Japanese is a painter.

u3=DeleteCases[u2,{Japanese,Except[painter],__}|{Except[Japanese],painter,__}];
Length[u3]

The Italian drinks tea.

u4=DeleteCases[u3,{Italian,_,_,Except[tea],__}|{Except[Italian],_,_,tea,__}];
Length[u4]

Note that with the command

DeleteCases[u3, {Italian, __, Except[tea], __}|{Except[Italian],__,tea,__}];
Length[%]

we wrongly delete more cases. The reason is that the position of the drinks results undefined and the presence of say, the zebra, qualifies as a non-tea

The Norwegian lives in the first house on the left.

u5=DeleteCases[u4,{Norwegian,___,Except[1]}|{Except[Norwegian],___,1}];
Length[u5]

The photographer breeds snails.

u6=DeleteCases[u5,{_,photographer,Except[snails],__}|{_,Except[photographer],snails,__}];
Length[u6]

The diplomat lives in the yellow house.

u7=DeleteCases[u6,{_,diplomat,__,Except[yellow],_}|{_,Except[diplomat],__,yellow,_}];
Length[u7]

Milk is drunk in the middle house.

u8=DeleteCases[u7,{__,Except[milk],_,3}|{__,milk,_,Except[3]}];
Length[u8]

The owner of the green house drinks coffee.

u9=DeleteCases[u8,{__,Except[coffee],green,_}|{__,coffee,Except[green],_}];
Length[u9]

The violinist drinks orange juice.

u10=DeleteCases[u9,{_,violinist,_,Except[orangeJuice],__}|{_,Except[violinist],_,orangeJuice,__}];
Length[u10]

At this point we might think we have to choose a set of five from u10 using the rest of the clues; still a tall order:

Binomial[133,5]

Or rather we have to choose one of each set corresponding to different nationalities:

n=Cases[u10,#]&/@{{English,__},{Spaniard,__},{Japanese,__},{Italian,__},{Norwegian,__}};
Short[n,6]

The different cases are distributed by nationalities in the following amounts

Length/@n

That is, there are 25 possible patterns for the Englishman, 21 for the Spaniard, etc. So, in total we will have:

Times@@%

although this amount is lesser than before, it is still quite intimidating. We have to choose independent sets of five elements, that is, 5-sets having empty intersections. For instance, choosing all independent pairings of the first two nationalities we have the following list comprising 216 elements

u11=Flatten[Map[(e=#;{e,#}&/@Select[(Subscript[n, [[2]]]),#⋂e=={}&])&,(Subscript[n, [[1]]])],1];
Short[u11,6]

selected out of 25 x 21=525

We enlarge u11 to cover the third nationality producing independent triads

u12=Flatten[Map[(e=#;Append[e,#]&/@Select[(Subscript[n, [[3]]]),#⋂Flatten[e]=={}&])&,u11],1];
Short[u12,6]

The amount increased, so it is no surprise that it will increase again when considering the independent quartets

u13=Flatten[Map[(e=#;Append[e,#]&/@Select[(Subscript[n, [[4]]]),#⋂Flatten[e]=={}&])&,u12],1];
Short[u13,6]

and independent quintics:

u14=Flatten[Map[(e=#;Append[e,#]&/@Select[(Subscript[n, [[5]]]),#⋂Flatten[e]=={}&])&,u13],1];
Short[u14,6]

Can the reader explain why the following two numbers coincide?

Length/@{u13,u14}

The amount of quintics has fallen down to a managable quantity. Let us sort the quintics by house number:

u15=Sort[#,Last[#1]<Last[#2]&]&/@u14;

And carry on considering the clues on the quintics:

The Norwegian´s house is next to the blue one.

u16=Cases[u15,{___,{Norwegian,__},{__,blue,_},___}|{___,{__,blue,_},{Norwegian,__},___}];
Length[u16]

Note that we use the pattern with three underscores for the first time and we use one, two and three underscores together to convey the clue.

The fox is in a house next to that of the physician.

u17=Cases[u16,{___,{__,fox,__},{_,physician,__},___}|{___,{_,physician,__},{__,fox,__},___}];
Length[u17]

The horse is in a house next to that of the diplomat.

u18=Cases[u17,{___,{__,horse,__},{_,diplomat,__},___}|{___,{_,diplomat,__},{__,horse,__},___}];
Length[u18]

The green house is to the right of the white house.

u19=Cases[u18,{___,{__,white,_},{__,green,_},___}]

Or, more succinctly

TableForm[Transpose[Most/@u19[[1]]],TableHeadings->{{"nationalities","jobs","pets","drinks","house's colors"},Range[5]}]

So, the answer of the riddle is: The Japanese owns the zebra. Moreover, the solution turns out to be unique - it would be more elegant to have had many soltuions, all of them pointing out the zebra belonging to the Japanese. We will tackle such problem in a moment.

An easier puzzle

Consider now the following easier version of a similar puzzle.

There are three men, all with different nationalities, pets and favorite drinks and living in houses of different numbers. The following facts are known:

The man in the middle house drinks milk.

The Spaniard owns the dog.

The Ukranian drinks the tea.

The Norwegian lives in the first house.

The Norwegian lives next to the tea-drinker.

The juice-drinker owns the fox

Who owns the zebra?

We apply all the steps used first to setup variable u, then trim it, then to choose triads from it.

nationalities = {Spaniard,Ukranian,Norwegian};
pets = {dog,fox,zebra};
drinks = {milk,tea,juice};
houses = {1, 2, 3};

u=Flatten[Outer[List,nationalities,pets,drinks,houses],3];
Length[u]
Short[u,4]

In this case there are not that many choices

Binomial[81,3]

So, we proceed generating them:

u1 = Subsets[u, {3}];
Short[u1, 6]

u1[[1]]

We select now only those few that include 12 different items

u2=Select[u1, Length[Union[Flatten[#]]] == 12 &];
Length[u2]

We now sequentially apply the clues

The man in the middle house drinks milk.

u3=Cases[u2,{___,{__,milk,3},___}];
Length[u3]

Alternatively we could have used:

u3=DeleteCases[u2,{___,{__,Except[milk],3},___}|{___,{__,milk,Except[3]},___}];
Length[u3]

The Spaniard owns the dog.

u4=Cases[u3,{___,{Spaniard,dog,__},___}];
Length[u4]

The Ukranian drinks the tea

u5=Cases[u4,{___,{Ukranian,_,tea,__},___}];
Length[u5]

The Norwegian lives in the first house.

u6=Cases[u5,{___,{Norwegian,__,1},___}];
Length[u6]

The juice-drinker owns the fox

u7=Cases[u6,{___,{_,fox,juice,_},___}]

that is

TableForm[Transpose[Most/@Reverse[u7[[1]]]],TableHeadings->{{"nationalities","pets","drinks"},Range[3]}]

Alternatively, we could have arrived to this result in one step:

Cases[Cases[Cases[Cases[Cases[u2,{___,{__,milk,3},___}],{___,{Spaniard,dog,__},___}],{___,{Ukranian,_,tea,__},___}],{___,{Norwegian,__,1},___}],{___,{_,fox,juice,_},___}]

So, the answer is: The Ukranian owns the zebra. Note we could not have used the following statement

Short[Cases[u2, {___, {__, milk, 3}, ___}| {___, {Spaniard, dog, __}, ___}| {___, {Ukranian, _, tea, __}, ___}| {___, {Norwegian, __, 1}, ___}|{___, {_, fox, juice, _}, ___}],6]

To see why consider the first triad. It passes as a valid case because it is of the form  {___, {Spaniard, dog, __}, ___}, even though it does not fit the rest of the cases. It is a pity the following command cannot be used (as of version 6) to get the answer in one go.

Cases[u2, {___, {__, milk, 3}, ___} && {___, {Spaniard, dog, __}, ___} && {___, {Ukranian, _, tea, __}, ___} && {___, {Norwegian, __, 1}, ___} && {___, {_, fox, juice, _}, ___}]

A more difficult puzzle

The fact that the first ten clues allowed us to substantially trim variable u renders the zebra puzzle relatively easy to handle by computer. Consider now the following variation.

There are five houses on a street. Each house of a different color and inhabited by a different person. Each person has a different preferred beverage, preferred food, and pet animal. We are offered the following clues:

The doctor lives in the red house and likes vodka.

The person who lives in the middle house drinks milk.

The person who likes tea has a ferret.

The physicist has only one neighbour.

The person who likes orange juice has only one neighbor.

The physicist does not live in the white house.

The green house is immediately to the left of the white house.

The mathematician lives two houses from the physicist.

The person who likes olives lives right next to the person who has a cat.

The physicist lives right next to the blue house.

The zebra lives right next to the fish and to the left of the ferret owner house.

Now, the question is: In what house's number lives the owner of the zebra?

We setup variable u, filling in the data that is not mentioned

jobs = {doctor,physicist,mathematician,j4,j5};
pets = {cat,fish,ferret,zebra,p5};
drinks = {milk,tea,orange,vodka,d5};
foods={olives,f2,f3,f4,f5};
colors = {green,white,blue,red,c5};
houses={1,2,3,4,5};

And setup variable u:

u = Flatten[Outer[List,  jobs, pets, drinks,foods, colors,houses],5];
Length[u]
Short[u, 4]

We are faced witht he same amount of combinations of 5-tuples as before:

Binomial[15625,5]

(in reality we should consider only

((5!)^6)

which is not a great relief!) Let us trim variable u using the clues.

The doctor lives in the red house and likes vodka.

u1 = DeleteCases[u, {doctor, __, Except[red], _}|{Except[doctor],__,red,_}|{doctor,_,Except[vodka],__}|{Except[doctor],_,vodka,__}];
Length[u1]

The person who lives in the middle house drinks milk.

u2 = DeleteCases[u1, {_,_, Except[milk],__, 3}|{_,_, milk,__, Except[3]}];
Length[u2]

The person who likes tea has a ferret.

u3 = DeleteCases[u2, {_,ferret, Except[tea],__}|{_,Except[ferret], tea,__}];
Length[u3]

The physicist has only one neighbour.

u4 = DeleteCases[u3, {physicist, __, Except[1|5]}];
Length[u4]

Note we cannot use the following command to convey this clue as it will erase the physicist from u3

DeleteCases[u3, {physicist, __, Except[1]} | {physicist, __, Except[5]}];
Cases[%, {physicist, __} ]

The person who likes orange juice has only one neighbor.

That person has to live at house 1 or at house 5

u5= DeleteCases[u4, {_,_,orange,__,Except[1|5]}];
Length[u5]

The physicist does not live in the white house.

u6 = DeleteCases[u5, {physicist, __,white,_}];
Length[u6]

The next clues provide partial subclues  that we can use to further trim u.

The green house is immediately to the left of the white house. Stage 1

This means two things: the green house cannot be number 5 and the white house cannot be number 1

u7 = DeleteCases[u6, {__, green,5}|{__,white,1}];
Length[u7]

The mathematician lives two houses from the physicist. Stage 1

Meaning, the mathematician nor the physicist can live at house 3

u8 = DeleteCases[u7, {mathematician,__,3}|{physicist,__,3}];
Length[u8]

The person who likes olives lives right next to the person who has a cat. Stage 1

This means two things: the  person x who likes olives cannot live at the first house, the person y who has a pet cat cannot live at house number 5. Also, x cannot have a pet cat and y cannot like olives

u9 = DeleteCases[u8, {__, olives,_, 1} | {_,cat,__, 5}|{_,cat,_,olives,__}];
Length[u9]

The physicist lives right next to the blue house. Stage 1

u10= DeleteCases[u9, {physicist,__, 1} | {__,blue, 5}|{physicist,__,blue,_}];
Length[u10]

Of what color can the physicist house be?

Union[Cases[u10,{physicist,__,c_,i_}:>{c,i}]]

So, the physicist lives at house 5 and its color is c5. Then the mathematician must live at house 2

u11=DeleteCases[u10,{mathematician,__,Except[2]}|{Except[physicist],__,5}|{__,c5,Except[5]}|{__,Except[c5],5}];
Length[u11]

The cases for each color are distributed as :

n=Map[Cases[u11,{__,#,_}]&,colors];
Length/@n

Choosing the green house first

Pairing up each of the 230 possibilities for the green house with an independant selection for the white house

u12=Flatten[Map[(e=#;{e,#}&/@Select[(Subscript[n, [[2]]]),#⋂e=={}&])&,(Subscript[n, [[1]]])],1];
Short[u12,6]

Out of 230x158=36340.

The green house is immediately to the left of the white house. Stage 2

u13=Select[u12,First[#][[-1]]+1==Last[#][[-1]]&];
Short[u13,6]

Do you think the green house can be house number 1? Yes:

Length[Cases[u13,{{__,green,1},_}]]

To further trim this amount, we can apply stages 2 of the following clues

The person who likes olives lives right next to the person who has a cat. Stage 2

combining this clue and the previous one,  if the inhabitant of the green house x likes olives, the inhabitant of the white house y cannot haver a pet cat and secondly, if y has a pet cat then x cannot like olives.

u14=DeleteCases[u13,{{_,Except[cat],__},{__,olives,_,_}}|{{__,olives,_,_},{_,cat,__}}];
Length[u14]

Now, let us produce independant triples with the choices for the blue house

u15=Flatten[Map[(e=#;Append[e,#]&/@Select[(Subscript[n, [[3]]]),#⋂Flatten[e]=={}&])&,u14],1];
Short[u15,6]

out of  2680x230=616400.

Note that we cannot conclude that, as

Cases[u14,{___,{physicist,__},___}]

the data is inconsistent. We have not finished constructing the independant quinticts. Let us build quartics now:

u16=Flatten[Map[(e=#;Append[e,#]&/@Select[(Subscript[n, [[4]]]),#⋂Flatten[e]=={}&])&,u15],1];
Short[u16,6]

out of

Length[u15] 54

Finally, independant quintics:

u17=Flatten[Map[(e=#;Append[e,#]&/@Select[(Subscript[n, [[5]]]),#⋂Flatten[e]=={}&])&,u16],1];
Short[u17,6]

out of

Length[u16] 35

Let us sort them by house number before applying the clues.

u18=Map[(h=#;Sort[h,Last[#1]<Last[#2]&])&,u17];

The person who likes olives lives right next to the person who has a cat. Stage 3

u19 = Cases[u18, {___, {_,cat, __}, {__,olives, __}, ___}];
Short[u19, 6]

The physicist lives right next to the blue house. Stage 2

u20=Cases[u19,{___,{__,blue,_},{physicist,__},___}];
Short[u20,6]

The zebra lives right next to the fish and to the left of the ferret owner house.

u21= Cases[u20, {___, {_, fish, __}, {_, zebra, __}, {_,ferret,__}, ___}];
Short[u21, 6]

So, our answer is:

Union[Cases[u21, {___,  {_, zebra, __,a_}, ___} :> a]]

The zebra lives at house number 3. There are 45 possible ways the problem can be solved, one is:

TableForm[Transpose[Most/@u21[[1]]]/. {f4|d5|j4|j5|f2|f3|f5|p5|c5->""},TableHeadings->{{"jobs","pets","drinks","foods","house's colors"},Range[5]}]

[1] Einstein Riddle
http://www.naute.com/puzzles/puzzle13.phtml

[2] Zebra puzzle
	http://en.wikipedia.org/wiki/Zebra_Puzzle

This work was finished at Wolfram Research Inc., in Champaign IL, USA, while the first author was invited as a Visiting Scholar. Their assistance and enthusiastic support is gratefully acknowledged. Our thanks are also given for the continuous support received from the University of Queretaro in Mexico.